package com.fwpsl.tree;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/7
 * @description: 树 满二叉树、完全二叉树，平衡二叉树
 */
public class Tree<T> {

    /**
     * 树的节点
     *
     * @param <T>
     */
    static class Node<T> {
        protected T val;
        protected Node<T> parent;
        protected Node<T> left;
        protected Node<T> right;

        public Node(T val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }

        public Node(T val, Node<T> left, Node<T> right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public T getVal() {
            return val;
        }

        public void setVal(T val) {
            this.val = val;
        }

        public Node<T> getParent() {
            return parent;
        }

        public void setParent(Node<T> parent) {
            this.parent = parent;
        }

        public Node<T> getLeft() {
            return left;
        }

        public void setLeft(Node<T> left) {
            this.left = left;
        }

        public Node<T> getRight() {
            return right;
        }

        public void setRight(Node<T> right) {
            this.right = right;
        }
    }

    /**
     * 树根节点
     */
    private Node<T> root;

    public Tree() {
        root = null;
    }

    public Tree(T rootVal) {
        root = new Node(rootVal);
    }

    public Node<T> getRoot() {
        return root;
    }

    public Node<T> addLeftTree(Node<T> node, T value) {
        if (node == null) {
            return null;
        }

        Node<T> tl = new Node(value);
        node.left = tl;
        tl.parent = node;
        return tl;
    }

    public Node<T> addRightTree(Node<T> node, T value) {
        if (node == null) {
            return null;
        }

        Node<T> tr = new Node(value);
        node.right = tr;
        tr.parent = node;
        return tr;
    }

    /**
     * 构建编号二叉树
     *
     * @param nodeNum
     * @return
     */
    public static Tree<Integer> newTree(Integer nodeNum) {
        Integer nodeVal = 1;
        Tree<Integer> tree = new Tree<>(nodeVal++);

        Queue<Tree.Node> queue = new LinkedList<>();
        queue.offer(tree.getRoot());
        while (!queue.isEmpty()) {
            Node<Integer> tn = queue.poll();

            Tree.Node tl = tree.addLeftTree(tn, nodeVal++);
            if (nodeVal > nodeNum) {
                break;
            }

            Tree.Node tr = tree.addRightTree(tn, nodeVal++);
            if (nodeVal > nodeNum) {
                break;
            }

            queue.offer(tl);
            queue.offer(tr);
        }

        return tree;
    }

    /**
     * 寻找路径，
     * 首先从开始节点到根节点的路径bList，再从结束节点到根节点依次遍历，找到首个在bList中的节点node1, 并生成路径eList。
     *
     * @param beginNode
     * @param endNode
     * @return
     */
    public static <T extends Comparable<T>> String path(Node<T> beginNode, Node<T> endNode) {
        if (beginNode == null || endNode == null) {
            return null;
        }

        // 开始节点到根节点的路径集合
        List<Node<T>> blist = new ArrayList<>();
        Node<T> current = beginNode;
        while (current != null) {
            blist.add(current);
            current = current.parent;
        }

        // 结束节点到根节点的路径集合。当路径节点eNode在bList中时，结束循环。
        List<Node<T>> elist = new ArrayList<>();
        Node<T> enode = endNode;
        while (enode != null) {
            if (blist.contains(enode)) {
                break;
            }

            elist.add(enode);
            enode = enode.parent;
        }

        // 输出路径， startNode -> eNode -> endNode
        StringJoiner joiner = new StringJoiner("->");
        for (int i = 0; i < blist.size(); i++) {
            joiner.add(String.valueOf(blist.get(i).getVal()));
            if (blist.get(i) == enode) {
                break;
            }
        }
        for (int i = elist.size() - 1; i >= 0; i--) {
            joiner.add(String.valueOf(elist.get(i).getVal()));
        }

        return joiner.toString();
    }

    public static void main(String[] args) {
        Tree<Integer> tree = newTree(16);

        // 输出两个节点的路径
        Node<Integer> beginNode = tree.root.left.left.left;
        Node<Integer> endNode = tree.root.right.left.left;
        System.out.println(path(beginNode, endNode));
    }
}
